Power optimization for connectivity problems

Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MPb-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b(v), the Min-Power k-node Connected Spanning Subgraph problem (MPk-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MPk-CSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MPk-EDP). We give an O(log⁴ n)-approximation algorithm for MPb-EC. This gives an O(log⁴ n)-approximation algorithm for MPk-CSS for most values of k, improving the best previously known O(k)-approximation guarantee. In contrast, we obtain an approximation algorithm for ECSS, and for its variant in directed graphs (i.e., MPk-EDP), we establish the following inapproximability threshold: MPk-EDP cannot be approximated within O(2^log1-ε n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time. This paper was done when V. S. Mirrokni was at Computer Science and Artificial Intelligence Laboratory, MIT.     

Packing directed cycles efficiently

Let G be a simple digraph. The dicycle packing number of G, denoted ν_c(G), is the maximum size of a set of arc-disjoint directed cycles in G. Let G be a digraph with a nonnegative arc-weight function w. A function ψ from the set C of directed cycles in G to R₊ is a fractional dicycle packing of G if ∑_e∈C∈Cψ(C)?w(e) for each e∈E(G). The fractional dicycle packing number, denoted , is the maximum value of ∑_C∈Cψ(C) taken over all fractional dicycle packings ψ. In case w≡1 we denote the latter parameter by .Our main result is that where n=|V(G)|. Our proof is algorithmic and generates a set of arc-disjoint directed cycles whose size is at least ν_c(G)-o(n²) in randomized polynomial time. Since computing ν_c(G) is an NP-Hard problem, and since almost all digraphs have ν_c(G)=Θ(n²) our result is a FPTAS for computing ν_c(G) for almost all digraphs.The result uses as its main lemma a much more general result. Let F be any fixed family of oriented graphs. For an oriented graph G, let ν_F(G) denote the maximum number of arc-disjoint copies of elements of F that can be found in G, and let denote the fractional relaxation. Then, . This lemma uses the recently discovered directed regularity lemma as its main tool.It is well known that can be computed in polynomial time by considering the dual problem. We present a polynomial algorithm that finds an optimal fractional dicycle packing. Our algorithm consists of a solution to a simple linear program and some minor modifications, and avoids using the ellipsoid method. In fact, the algorithm shows that a maximum fractional dicycle packing with at most O(n²) dicycles receiving nonzero weight can be found in polynomial time.     

Pattern projection for subpixel resolved imaging in microscopy

In this paper, we present a new approach providing super resolved images exceeding the geometrical limitation given by the detector pixel size of the imaging camera. The concept involves the projection of periodic patterns on top of the sample, which are then investigated under a microscope. Combining spatial scanning together with proper digital post-processing algorithm yields the improved geometrical resolution enhancement. This new method is especially interesting for microscopic imaging when the resolution of the detector is lower than the resolution due to diffraction.     

Coordination chemistry of corroles with focus on main group elements

The discovery of facile methodologies for the synthesis of triarylcorroles initiated extensive research on the corresponding metal complexes, ranging from elucidation of their fundamental physical properties to utilization of their chemical reactivity for many applications. This review focuses on the coordination chemistry of main group elements chelated by tetradentate and trianionic 5,10,15-triarylcorroles, which led to the elucidation of unique photophysical, crystallographic and electrochemical characteristics of these complexes. The facile access to a variety of complexes in which these and other properties can be relatively easily tuned allows for the introduction of metallocorroles as key components in advanced systems, such as for photovoltaic cells and imaging procedures in living organism.     

Four-electron oxygen reduction by brominated cobalt corrole

The carbon-supported cobalt(III) complex of β-pyrrole-brominated 5,10,15-tris(pentafluorophenyl)corrole [Co(tpfc)Br(8)/C] is introduced as a nonplatinum alternative for electrocatalytic oxygen reduction in aqueous solutions. Through systematic work, the basic kinetic parameters of this reaction were studied, using rotating ring disk electrode electrochemical methods in the pH range of 0-11. Pronounced catalytic activity was detected in acid solutions along with shifts of the Co(II)/Co(III) and O(2) redox couples to more positive values (onset of 0.56 V at pH 0). A series of independent measurements have been used to prove that the dominant mechanism for oxygen reduction by Co(tpfc)Br(8)/C catalysis is the direct four-electron pathway to water.     

Two-dimensional temporal coherence coding for super resolved imaging

In this paper, we present an approach that can be used for transmission of 2D spatial information through space-limited systems capable of transmitting even only a single spatial pixel. The input 2D object is illuminated with temporally incoherent illumination. The axial coherence length is very short and it equals only a few microns. Attached to the input object spatial random phase mask generates different axial shift for every pixel of the input. The temporal delays of the encoding (axial shifts) of every pixel are longer than the coherence length of the illuminating source. Therefore no temporal correlation exists between the various pixels of the input. A lens combines all spatial pixels into one point at its focal plane. Although the various spatial pixels were mixed together, since the random mask provided axial delay which was larger than the coherence length of the light source, the orthogonality between the spatial content of every pixel is preserved. The decoding system includes a lens that is positioned at the output of the resolution reduction system and it converts the output light into a plane wave containing all the spatial information of the original image mixed together in all of its pixels. By interfering this plane wave with the same plane wave after passing through the same random spatial coding mask, the spatial information of every pixel of the input object is recovered.     

The effect of grana and inter-grana components of chloroplasts on green light transmission: A preliminary study

In this paper we simulate for the first time the propagation of green light through grana and inter-grana components of chloroplasts. Those components are nano-metric structures and thus regular estimation of the propagation of light cannot be exact without taking into account diffraction effects. The numerical investigation presented in this paper solves Maxwell wave equation using the finite-difference time-domain (FDTD) numerical approach to analyze the propagation of light through a chloroplast model.     

Common-path phase-shifting digital holographic microscopy: A way to quantitative phase imaging and superresolution

We present an experimental setup useful for complex amplitude evaluation and phase image quantification of three-dimensional (3-D) samples in digital holographic microscopy (DHM). It is based on a common-path interferometric configuration performed by dividing the input plane in two contiguous regions and by placing a translation grating near to the Fourier plane. Then, complex amplitude distribution of the sample under test is recovered with phase-shifting standard method obtained by moving the grating using a linear motion stage. Some experimental results of an USAF resolution test are presented for different numerical aperture (NA) microscope lenses. In a second part, the proposed setup is tested under superresolution purposes. Based on the object’s spectrum shift produced by off-axis illumination, we use time multiplexing to generate a synthetic aperture enlargement that improves the final image resolution. Experimental results for the case of a biosample (human red blood cells) and a commercial low NA microscope lens validates the suggested superresolution approach.     

N-Substituted Corroles: A Novel Class of Chiral Ligands

Although known for almost 35 years , N-substituted corroles have only now been recognized as being chiral. Several examples of these species were prepared in a facile two-step synthesis and separated into their enantiomers by HPLC. The zinc(II ) complex of the corrole shown schematically was also synthesized.